/*
 *	TODO 1.pointer transmit on call function
 *		 2. avoid make slice in Merge Function
 */

package sort

import (
//"fmt"
)

/*
type MergeValue interface {
	Less(value MergeValue) bool // TODO 1.
}*/

type MergeData interface {
	Less(i, j int) bool
	Index(i int) interface{}
	Copy(i int, v interface{})
}

func MergeSort(data MergeData, slice []interface{}, left, right int) {
	if left >= right {
		//	fmt.Printf("MergeSort left:%d >= fight:%d\n", left, right)
		return
	}

	mid := (right + left) / 2
	//1. sort left -> mid
	//fmt.Printf("1: left:%d mid:%d\n", left, mid)
	MergeSort(data, slice, left, mid)

	//2. sort mid -> right
	//fmt.Printf("2: mid+1:%d right:%d\n", mid+1, right)
	MergeSort(data, slice, mid+1, right)

	//3. merge left and right
	//fmt.Printf("3: l:%d m+1:%d r:%d\n", left, mid+1, right)
	Merge(data, slice, left, mid+1, right)
}

func Merge(data MergeData, slice []interface{}, left, mid, right int) {
	//tmp := make([]interface{}, 0) // TODO 2.

	i := left
	j := mid
	start := left

	for i < mid && j <= right {
		//	fmt.Printf("data.Less(%d,%d) = %v\n", i, j, data.Less(i, j))
		if data.Less(i, j) {
			slice[start] = data.Index(i)
			i++
		} else {
			slice[start] = data.Index(j)
			j++
		}
		start++
	}

	for i < mid {
		slice[start] = data.Index(i)
		start++
		i++
	}

	for j <= right {
		slice[start] = data.Index(j)
		start++
		j++
	}
	//fmt.Println(slice)
	num := right - left + 1
	for i := 0; i < num; {
		data.Copy(right, slice[right])
		right--
		i++
	}
	//copy(data[right:left], tmp)
}

/*
func MergeLess(data []interface{}, fron, back uint32) bool {
	return data[fron].(MergeValue).Less(data[back].(MergeValue))
}*/
